package leetcode.L1000;

import java.util.LinkedList;
import java.util.Queue;

public class EX547 {
//dfs方法
/*
public static void main(String[] args) {
    int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
    int n = isConnected.length;
    int [] v = new int[n];
    int res = 0;

    for (int i = 0; i < n ; i++) {
            if(v[i]==0){
                dfs(isConnected,v,n,i);
                res++;
            }
    }
    System.out.println(res);
}
public static void dfs(int[][] isConnected,int[] v,int n ,int i){
    for (int j = 0; j < n; j++) {
        if(isConnected[i][j]==1&&v[j]==0){
            v[j]=1;
            dfs(isConnected,v,n,j);
        }
    }
}
*/

public static void main(String[] args) {
    int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
    int n = isConnected.length;
    int v[] = new int[n];
    int res = 0;
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n ; i++) {
        if(v[i]==0){
         queue.offer(i);
         while (!queue.isEmpty()){
             int j = queue.poll();
             v[j] = 1;
             for (int k = 0; k < n  ; k++) {
                 if(isConnected[j][k]==1&&v[k]==0){
                     queue.offer(k);
                 }
             }
         }
         res++;
        }
    }
    System.out.println(res);
}



}
